//#include<iostream>
//using namespace std;
//int main() {
//	int n, k;
//	scanf_s("%d", &n);
//	scanf_s("%d", &k);
//	int* a = (int*)calloc(n, sizeof(int));
//	for (int i = 0; i < n; i++)
//		scanf_s("%d", &a[i]);
//	int i = 0, j = n - 1;
//	int* p = (int*)calloc(k, sizeof(int)), * q = (int*)calloc(k, sizeof(int));
//	for (int x = 0; x < k; x++)
//		scanf_s("%d %d", &p[x], &q[x]);
//	for (int x = 0; x < k; x++) {
//		i = n / 4;
//		j = n / 4 * 3;
//		if (a[i] < p[x])
//			while (a[i] < p[x] && i < n)
//				i++;
//		else
//			while (a[i - 1] >= p[x] && i - 1 >= 0)
//				i--;
//		if (a[j] > q[x])
//			while (a[j] > q[x] && j >= 0)
//				j--;
//		else
//			while (a[j + 1] <= q[x] && j + 1 < n)
//				j++;
//		printf("%d\n", j - i + 1);
//
//		//for (i = 0, j = n - 1; i <= j;) {
//		//	if (a[i] < p[x]) {
//		//		i++;
//		//	}
//		//	if (a[j] > q[x])
//		//		j--;
//		//	if (a[i] >= p[x] && a[j] <= q[x]) {
//		//		/*for (int y = i; y <= j; y++) {
//		//			printf("%d", a[y]);
//		//			if (y == j)
//		//				printf("\n");
//		//			else
//		//				printf(" ");
//		//		}*/
//		//		printf("%d\n", j - i + 1);
//		//		break;
//		//		//}
//		//	}
//		//}
//
//	//int il, ir, jl, jr;
//	//for (int m = 0; m < k; m++) {
//	//	for (i = n / 2, j = n / 2, il = 0, ir = n - 1, jl = 0, jr = n - 1;;) {
//	//		//if (!((a[i - 1] <= p[m] && a[i] >= p[m]) || (a[i] <= p[m] && a[i + 1] >= p[m])) && ((a[j - 1] <= q[m] && a[j] >= q[m]) || (a[j] <= q[m] && a[j + 1] >= q[m])))
//	//		{
//	//			if (a[i] < p[m]) {
//	//				il = i;
//	//				i += (ir - il) / 2;
//	//			}
//	//			//else if (a[i] > p[m]) {
//	//			//	ir = i;
//	//			//	i -= (ir - il) / 2;
//	//			//}
//	//			if (a[j] > q[m]) {
//	//				jr = j;
//	//				j -= (jr - jl) / 2;
//	//			}
//	//			//else if (a[j] < q[m]) {
//	//			//	jl = j;
//	//			//	j += (jr - jl) / 2;
//	//			//}
//	//		}
//	//		if (a[i] >= p[m] && a[j] <= q[m]) {
//	//			while (i > 0 && a[i - 1] >= p[m])
//	//				i--;
//	//			while (j < n - 1 && a[j + 1] <= q[m])
//	//				j++;
//	//			printf("%d\n", j - i + 1);
//	//			break;
//	//		}
//	//	}
//	}
//	return 0;
//}